package com.yun.datastructure.tree.binarytree.leetcode;

import com.yun.datastructure.tree.binarytree.domain.TreeNode;

import java.util.LinkedList;

public class Leetcode104 {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int dl=maxDepth(root.left);
        int dr=maxDepth(root.right);
        return Math.max(dl,dr)+1;
    }

    public int maxDepth1(TreeNode root){
        LinkedList<TreeNode> stack=new LinkedList<>();
        TreeNode curr=root;
        TreeNode pop=null;
        int maxD=0;
        while (curr!=null||!stack.isEmpty()){
            if(curr!=null){
                stack.push(curr);
                curr=curr.left;
            }else {
                TreeNode peek=stack.peek();
                if(peek.right==null){
                    maxD=Math.max(maxD,stack.size());
                    pop=stack.pop();
                }else if(peek.right==pop){
                    pop=stack.pop();
                }else {
                    curr=peek.right;
                }
            }
        }
        return maxD;
    }
}
